package exercises.newcoder.solution;

import exercises.newcoder.util.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=202&&tqId=38717&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC8 重排链表</a>
 *
 * @author or2
 * @Description 将给定的单链表\ L L： L_0→L_1→…→L_{n-1}→L_ nL
 * 0
 * ​
 * →L
 * 1
 * ​
 * →…→L
 * n−1
 * ​
 * →L
 * n
 * ​
 * <p>
 * 重新排序为：L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…L
 * 0
 * ​
 * →L
 * n
 * ​
 * →L
 * 1
 * ​
 * →L
 * n−1
 * ​
 * →L
 * 2
 * ​
 * →L
 * n−2
 * ​
 * →…
 * 要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
 * @create 2021年09月14日 时间: 19:51
 */
public class ReorderList {
    public void reorderList(ListNode head) {
//        校验输入
        if (head == null) {
            return;
        }

//        二分查找 - 链表二等分
        ListNode p = head;
        ListNode q = p.next;
        while (q != null) {
            q = q.next;
            if (q == null) {
                break;
            }
            q = q.next;
            p = p.next;
        }
//        以 p 为头结点, 逆序后续链表(头插法)
        q = p.next;
        p.next = null;
        while (q != null) {
            ListNode qNext = q.next;
            q.next = p.next;
            p.next = q;
            q = qNext;
        }

//        进行合并 - 断两端
        q = p.next;
        p.next = null;
//        插入
        p = head;
        while (q != null) {
            ListNode qNext = q.next;
            if (p == null) {
                p = qNext;
                break;
            }
            q.next = p.next;
            p.next = q;
            p = q.next;
            q = qNext;
        }
    }
}
